home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / utils / unix / unzip-5.12 / unshrink.c < prev    next >
C/C++ Source or Header  |  1994-08-14  |  18KB  |  546 lines
  1. #include "unzip.h"
  2.  
  3. #ifdef NEW_UNSHRINK
  4.  
  5. /*---------------------------------------------------------------------------
  6.  
  7.   unshrink.c                     version 0.94                     26 Apr 94
  8.  
  9.   Shrinking is basically a dynamic LZW algorithm with allowed code sizes of
  10.   up to 13 bits; in addition, there is provision for partial clearing of
  11.   leaf nodes.  PKWARE uses the special code 256 (decimal) to indicate a
  12.   change in code size or a partial clear of the code tree:  256,1 for the
  13.   former and 256,2 for the latter.  See the notes in the code below about
  14.   orphaned nodes after partial clearing.
  15.  
  16.   This replacement version of unshrink.c was written from scratch.  It is
  17.   based only on the algorithms described in Mark Nelson's _The Data Compres-
  18.   sion Book_ and in Terry Welch's original paper in the June 1984 issue of
  19.   IEEE _Computer_; no existing source code, including any in Nelson's book,
  20.   was used.
  21.  
  22.   Memory requirements are fairly large.  While the NODE struct could be mod-
  23.   ified to fit in a single 64KB segment (as a "far" data structure), for now
  24.   it is assumed that a flat, 32-bit address space is available.  outbuf2 is
  25.   always malloc'd, and flush() is always called with unshrink == FALSE.
  26.  
  27.   Copyright (C) 1994 Greg Roelofs.  See the accompanying file "COPYING" in
  28.   the UnZip 5.11 (or later) source distribution.
  29.  
  30.   ---------------------------------------------------------------------------*/
  31.  
  32.  
  33. /* #include "unzip.h" */
  34.  
  35. #ifdef DEBUG
  36. #  define OUTDBG(c)  if ((c)=='\n') {PUTC('^',stderr); PUTC('J',stderr);}\
  37.                      else PUTC((c),stderr);
  38. #else
  39. #  define OUTDBG(c)
  40. #endif
  41.  
  42. typedef struct leaf {
  43.     struct leaf *parent;
  44.     struct leaf *next_sibling;
  45.     struct leaf *first_child;
  46.     uch value;
  47. } NODE;
  48.  
  49. static void  partial_clear  __((NODE *cursib));
  50.  
  51. static NODE *node, *bogusnode, *lastfreenode;
  52.  
  53.  
  54. int unshrink()
  55. {
  56. #ifdef MACOS
  57.     static uch *stacktop = NULL;
  58. #else
  59.     static uch *stacktop = stack + 8192 - 1;
  60. #endif
  61.     register uch *newstr;
  62.     int codesize=9, code, oldcode=0, len, KwKwK;
  63.     unsigned int outbufsiz;
  64.     NODE *freenode, *curnode, *lastnode=node, *oldnode;
  65.  
  66.  
  67. /*---------------------------------------------------------------------------
  68.     Initialize various variables.
  69.   ---------------------------------------------------------------------------*/
  70.  
  71. #ifdef MACOS
  72.     if (stacktop == NULL) stacktop = stack + 8192 - 1;
  73. #endif
  74.  
  75.     if ((node = (NODE *)malloc(8192*sizeof(NODE))) == (NODE *)NULL)
  76.         return PK_MEM3;
  77.     bogusnode = node + 256;
  78.     lastfreenode = node + 256;
  79.  
  80. #ifndef SMALL_MEM   /* always true, at least for now */
  81.     /* non-memory-limited machines:  allocate second (large) buffer for
  82.      * textmode conversion in flush(), but only if needed */
  83.     if (pInfo->textmode && !outbuf2 &&
  84.         (outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
  85.     {
  86.         free(node);
  87.         return PK_MEM3;
  88.     }
  89. #endif
  90.  
  91.     /* this stuff was an attempt to debug compiler errors(?) when had
  92.      * node[8192] in union work area...no clues what was wrong (SGI worked)
  93.     Trace((stderr, "\nsizeof(NODE) = %d\n", sizeof(NODE)));
  94.     Trace((stderr, "sizeof(node) = %d\n", sizeof(node)));
  95.     Trace((stderr, "sizeof(area) = %d\n", sizeof(area)));
  96.     Trace((stderr, "address of node[0] = %d\n", (int)&node[0]));
  97.     Trace((stderr, "address of node[6945] = %d\n", (int)&node[6945]));
  98.      */
  99.  
  100.     for (code = 0;  code < 256;  ++code) {
  101.         node[code].value = code;
  102.         node[code].parent = bogusnode;
  103.         node[code].next_sibling = &node[code+1];
  104.         node[code].first_child = (NODE *)NULL;
  105.     }
  106.     node[255].next_sibling = (NODE *)NULL;
  107.     for (code = 257;  code < 8192;  ++code)
  108.         node[code].parent = node[code].next_sibling = (NODE *)NULL;
  109.  
  110.     outptr = outbuf;
  111.     outcnt = 0L;
  112.     if (pInfo->textmode)
  113.         outbufsiz = RAWBUFSIZ;
  114.     else
  115.         outbufsiz = OUTBUFSIZ;
  116.  
  117. /*---------------------------------------------------------------------------
  118.     Get and output first code, then loop over remaining ones.
  119.   ---------------------------------------------------------------------------*/
  120.  
  121.     READBITS(codesize, oldcode)
  122.     if (!zipeof) {
  123.         *outptr++ = (uch)oldcode;
  124.         OUTDBG((uch)oldcode)
  125.         if (++outcnt == outbufsiz) {
  126.             flush(outbuf, outcnt, FALSE);
  127.             outptr = outbuf;
  128.             outcnt = 0L;
  129.         }
  130.     }
  131.  
  132.     do {
  133.         READBITS(codesize, code)
  134.         if (zipeof)
  135.             break;
  136.         if (code == 256) {   /* GRR:  possible to have consecutive escapes? */
  137.             READBITS(codesize, code)
  138.             if (code == 1) {
  139.                 ++codesize;
  140.                 Trace((stderr, " (codesize now %d bits)\n", codesize));
  141.             } else if (code == 2) {
  142.                 Trace((stderr, " (partial clear code)\n"));
  143. #ifdef DEBUG
  144.                 fprintf(stderr, "   should clear:\n");
  145.                 for (curnode = node+257;  curnode < node+8192;  ++curnode)
  146.                     if (!curnode->first_child)
  147.                         fprintf(stderr, "%d\n", curnode-node);
  148.                 fprintf(stderr, "   did clear:\n");
  149. #endif
  150.                 partial_clear(node);       /* recursive clear of leafs */
  151.                 lastfreenode = bogusnode;  /* reset start of free-node search */
  152.             }
  153.             continue;
  154.         }
  155.  
  156.     /*-----------------------------------------------------------------------
  157.         Translate code:  traverse tree from leaf back to root.
  158.       -----------------------------------------------------------------------*/
  159.  
  160.         curnode = &node[code];
  161.         newstr = stacktop;
  162.  
  163.         if (curnode->parent)
  164.             KwKwK = FALSE;
  165.         else {
  166.             KwKwK = TRUE;
  167.             Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
  168.               oldcode));
  169.             --newstr;   /* last character will be same as first character */
  170.             curnode = &node[oldcode];
  171.         }
  172.  
  173.         do {
  174.             *newstr-- = curnode->value;
  175.             curnode = curnode->parent;
  176.         } while (curnode != bogusnode);
  177.  
  178.         len = stacktop - newstr++;
  179.         if (KwKwK)
  180.             *stacktop = *newstr;
  181.  
  182.     /*-----------------------------------------------------------------------
  183.         Write expanded string in reverse order to output buffer.
  184.       -----------------------------------------------------------------------*/
  185.  
  186.         Trace((stderr, "code %4d; oldcode %4d; char %3d (%c); string [", code,
  187.           oldcode, (int)(*newstr), *newstr));
  188.         {
  189.             register uch *p;
  190.  
  191.             for (p = newstr;  p < newstr+len;  ++p) {
  192.                 *outptr++ = *p;
  193.                 OUTDBG(*p)
  194.                 if (++outcnt == outbufsiz) {
  195.                     flush(outbuf, outcnt, FALSE);
  196.                     outptr = outbuf;
  197.                     outcnt = 0L;
  198.                 }
  199.             }
  200.         }
  201.  
  202.     /*-----------------------------------------------------------------------
  203.         Add new leaf (first character of newstr) to tree as child of oldcode.
  204.       -----------------------------------------------------------------------*/
  205.  
  206.         /* search for freenode */
  207.         freenode = lastfreenode + 1;
  208.         while (freenode->parent)       /* add if-test before loop for speed? */
  209.             ++freenode;
  210.         lastfreenode = freenode;
  211.         Trace((stderr, "]; newcode %d\n", freenode-node));
  212.  
  213.         oldnode = &node[oldcode];
  214.         if (!oldnode->first_child) {   /* no children yet:  add first one */
  215.             if (!oldnode->parent) {
  216.                 /*
  217.                  * oldnode is itself a free node:  the only way this can happen
  218.                  * is if a partial clear occurred immediately after oldcode was
  219.                  * received and therefore immediately before this step (adding
  220.                  * freenode).  This is subtle:  even though the parent no longer
  221.                  * exists, it is treated as if it does, and pointers are set as
  222.                  * usual.  Thus freenode is an orphan, *but only until the tree
  223.                  * fills up to the point where oldnode is reused*.  At that
  224.                  * point the reborn oldnode "adopts" the orphaned node.  Such
  225.                  * wacky guys at PKWARE...